package com.Oct_Twelve;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 面试题 08.07. 无重复字符串的排列组合
 * 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 * https://leetcode.cn/problems/permutation-i-lcci/
 *
 * 2022/10/12 08:21
 */

public class Solution0807 {

    List<String> ans;
    boolean[] used;

    public String[] permutation(String S) {
        char[] array=S.toCharArray();
        used=new boolean[array.length];
        Arrays.fill(used,false);
        ans=new ArrayList<>();
        dfs(array,new StringBuilder());
        String[] res=new String[ans.size()];
        for (int i=0;i<ans.size();i++)
        {
            res[i]=ans.get(i);
        }
        return res;
        //return ans.toArray(new String[0]);
    }

    void dfs(char[] array,StringBuilder sb){
        if (sb.length()==array.length)
        {
            ans.add(sb.toString());
            return;
        }
        for (int i=0;i<array.length;i++)
        {
            if (used[i]) continue;
            used[i]=true;
            sb.append(array[i]);
            dfs(array,sb);
            sb.deleteCharAt(sb.length()-1);
            used[i]=false;
        }
    }

    public static void main(String[] args) {
        Solution0807 solution0807=new Solution0807();
        System.out.println(Arrays.toString(solution0807.permutation("qwe")));
    }
}
